In digital data communications systems, it is common for data packets transmitted over a communications channel to be corrupted by errors, e.g., when communicating in hostile environments. Wireless radio communications are often conducted in an especially hostile environment. The radio channel is subjected to a barrage of corrupting factors including noise, rapidly changing communications channel characteristics, multi-path fading, and time dispersion which may cause intersymbol interference, and interference from adjacent channel communications.
There are numerous techniques that may be employed by a receiver to detect such errors. One example of an error detection technique is the well-known cyclic redundancy check (CRC). Other techniques used in packet data communications employ more advanced types of block codes or convolutional codes to accomplish both error detection and error correction. For both error detection and error correction, channel coding is applied which adds redundancy to the data. When the information is received over the communications channel, the received data is decoded using the redundancy to detect if the data has been corrupted by errors. The more redundancy built into a unit of data, the more likely errors can be accurately detected, and in some instances, corrected using a forward error correcting (FEC) scheme. In a pure FEC scheme, the flow of information is uni-directional, and the receiver does not send information back to the transmitter if a packet decoding error occurs.
In many communications systems, including wireless communications, it is desirable to have a reliable data delivery service that guarantees delivery of data units sent from one machine to another without duplication of data or data loss. Most such reliable data delivery protocols use a fundamental retransmission technique where the receiver of the data responds to the sender of the data with acknowledgments and/or negative acknowledgments. This technique is commonly known as automatic repeat request (ARQ) transaction processing. Coded data packets are transmitted from a sender to a receiver over a communications channel. Using the error detection bits (the redundancy) included in the coded data packet, each received data packet is processed by the receiver to determine if the data packet was received correctly or corrupted by errors. If the packet was correctly received, the receiver transmits an acknowledgment (ACK) signal back to the sender. If the receiver detects errors in the packet, it may also send an explicit negative acknowledgment (NACK) to the sender. When the NACK is received, the sender can retransmit the packet. In a pure ARQ system, the channel code is only used for error detection.
In hybrid ARQ (HARQ), features of a pure FEC scheme and a pure ARQ scheme are combined. Error correction and error detection functions are performed along with ACK/NACK feedback signaling. The channel code in a hybrid ARQ scheme may be used for both error correction and error detection. Alternatively, two separate codes can be used: one for error correction and one for error detection. A NACK signal is sent back to the transmitter if an error is detected after error correction. The erroneously received data packet in this first type of hybrid ARQ system is discarded.
A more efficient hybrid ARQ scheme is to save the erroneously received and negatively acknowledged data packet and then combine it in some way with the retransmission. Hybrid ARQ schemes that use packet combining are referred to as hybrid ARQ with combining. In a hybrid ARQ combining scheme, the “retransmission” may be an identical copy of the original packet. If the retransmission is identical to the original transmission, the individual symbols from multiple packets are combined to form a new packet consisting of more reliable symbols. Alternatively, the retransmission may use incremental redundancy (IR). In IR packet combining, additional parity bits are transmitted which makes the error correction code more powerful than, and generally superior to, identical packet combining.
There are systematic and non-systematic FEC channel encoders. A systematic encoder creates code-words by appending redundant bits, sometimes called parity bits, to a block of information bits. A non-systematic encoder maps a set of information bits into a completely different set of coded bits. One class of powerful systematic codes is turbo codes. A turbo encoder uses at least two recursive convolutional encoders separated by an interleaver. Information bits are sent directly to the first encoder, and via the interleaver to the second encoder. The turbo encoded codewords include the original information bits (i.e., the systematic bits) and additional parity bits from the first and second encoders. Because the systematic bits are used in both the first and second encoders, the systematic bits are more important to the decoder at the receiver than the parity bits. Indeed, if the systematic bits are lost, it may be impossible for the decoder to correctly decode the data packet even if a substantial number of parity bits are subsequently received.
Both systematic and non-systematic codes may be used as the FEC code in a hybrid ARQ with combining scheme. However, the use of IR packet combining may be more difficult to combine with a channel code in which different code bits have different importance to the encoder. The use of turbo codes and IR combining, for example, is problematic because when a new data packet is transmitted for the first time, all systematic bits in the first transmission are included which ensures good performance of the turbo decoder. In IR packet combining, any retransmissions contain parity bits but not the systematic bits. There is a problem if the receiver completely misses the original transmission or the original transmission is so corrupted that it is useless to the decoder. Because subsequent retransmissions contain additional parity bits without the systematic bits, the data packet may not be correctly decoded. If the channel is highly unreliable, for example a radio channel, this lost original packet scenario may occur relatively often, triggering a large number of unnecessary retransmissions and delays resulting in decreased efficiency and throughput.
It is an object of the present invention to increase throughput and decrease delay in a packet data communications system.
It is an object of the present invention to provide an improved and more flexible hybrid ARQ scheme.
It is an object of the present invention to overcome problems that occur when using a hybrid ARQ with packet combining scheme over an unreliable communication channel where some coded bits are more important to decoding than other coded bits.
In data packet transmissions between a transmitter and a receiver, a data packet includes a first type of bits and second type of bits. In the preferred embodiment, the first type of bits is more important to decoding the data packet at the receiver than the second type of bits. For example, the first type of bits may include actual information bits, or systematic bits (actual information bits plus other bits like tail bits), while the second type of bits may include parity bits. Without the actual information bits, it may be quite difficult or even impossible to accurately decode the data packet just using the parity bits. When a packet is negatively acknowledged by the receiver, the transmitter retransmits information that is to be used in a subsequent decoding operation at the receiver. Such a retransmission includes the second type of bits. In one embodiment of the invention, retransmission may also include the first type of bits as well. In another preferred embodiment, the second type of bits are retransmitted without the first type of bits.
If a data packet is detected as absent or otherwise substantially corrupted, a LOST signal is sent to the transmitter rather than a negative acknowledgment. In response to the LOST signal, the transmitter sends a first retransmission to the receiver including the first type data bits in the packet, and preferably, also second type bits as well. That first retransmission is decoded, and if not successful, a negative acknowledgment is sent to the transmitter. In response to the negative acknowledgment, the transmitter in a preferred embodiment sends a second retransmission that includes second type bits without first type bits. In another embodiment, both types of bits are retransmitted.
An example receiver includes transceiving circuitry for receiving a coded data packet transmitted over a communications channel. An initially-transmitted, coded data packet includes both first and second type bits. If the absence of an expected packet is detected, packet processing circuitry transmits a LOST signal to the transmitter. A retransmission of the expected packet, including at least the first type bits and possibly the second type bits as well, is decoded. In addition, if a received coded data packet is substantially corrupted, a LOST signal may also be sent to the transmitter. The packet processing circuitry includes a buffer for storing received packet information, a combiner for combining buffered information with retransmitted information, a decoder for decoding an output of the combiner, and a controller for controlling the operation of the buffer, combiner, and decoder. In a preferred, example embodiment, the buffer and combiner perform an incremental redundancy operation. If decoding of the first retransmission is not successful, but the received data is believed to be useful in subsequent decoding attempts, then a negative acknowledgment is sent to the transmitter. In response, a second retransmission is received, including a set of the second type of bits either with or without the first type of bits depending upon the implementation.
An example transmitter includes a signal processor for processing data to be transmitted and generating corresponding systematic bits and parity bits. A combiner selectively receives one or both of systematic and parity bits from the signal processor and generates a coded data packet. Transceiving circuitry transmits the coded data packet over the communications channel. A controller controls which bits are selected by the combiner to generate the coded data packet based on the feedback signal from the receiver. When a negative acknowledgment is received, parity bits corresponding to the systematic bits are retransmitted over the channel to the receiver. When (1) a LOST signal is received or (2) no acknowledgment or no negative acknowledgment is received for a coded data packet, the systematic bits and possibly some parity bits are transmitted over the communications channel to the receiver. In one example embodiment, the systematic bits are retransmitted along with a set of parity bits originally transmitted with the systematic bits. Alternatively, the systematic bits are retransmitted with a set of parity bits different from those originally transmitted. After the first retransmission in response to (1) or (2), if the transmitter receives a negative acknowledgment in response to the first retransmission, a set of parity bits associated with the systematic bits is retransmitted with or (preferably) without the systematic bits.